package com.tom.architect02.leetcode;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    // 暴力破解
    // 原数组：[2,7, 11,15] target 9
    public int[] towSum(int[] nums, int target) {
        // hashMap接近O(1)的散列列表。不在扩容。
        // jdk1.8后，用的是红黑树，链表计比较长接近O(logn)，最差O(n)
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        // O(n平方)
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i]; // 得到差值。
            if (map.containsKey(diff)) { // 判断是否包含key。
                // 找到了，构建数据返回，map.get(diff)是之前的索引，i是对应被加数的索引。
                // 返回找到的2个数的索引数组。
                return new int[]{map.get(diff), i};
            }
            // 没找到, 将数据和对应的索引存起来。
            map.put(nums[i], i); // 存起来key存数据值， value存index索引。
        }
        return null;
    }

    // 一种取巧实现的方式。空间换时间。但是值是[2048,0,24,89] t=24 就会出错。
    public int[] towSum2(int[] nums, int target) {
        Integer[] temp = new Integer[2048];
        int diff = 0;
        for (int i = 0; i < nums.length; i++) {
            diff = target - nums[i]; // target 与当前值的差值。
            Integer index = temp[diff & 2047];
            if (index != null) {
                return new int[]{index, i}; // 找到了，构建int数组返回。
            }
            // 存起来
            temp[nums[i] & 2047] = i;
        }
        return null;
    }


    // String to int
/*    int mAtoi(string str) {
        int index = 0;
        int len = str.length();
        long res = 0; // 避免越界了

        while(str[index] == ' ') {
            index ++;
        }
        int negative = 1; // 正负符号
        if(str[index] == '-'){
            index ++;
            negative = -1;
        } else if (str[index] == '+'){
            index ++;
        }
        if(index == len) return 0;

        while(index < len) {
            char c = str[index++];
            if(c>'9' || c<'0') break;

            res = res*10 + (c-'0');
            if(res * negative > INT_MAX) {
                return INT_MAX;
            } else if(res * negative > INT_MIN) {
                return INT_MIN;
            }
        }
        return res * negative; // 处理正负数
    }*/


}
